跳到主要内容

Hamming 码

经典

定义生成矩阵

G=(0001111011001110101011111111)G=\left(\begin{array}{lllllll}0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right)

称它的行向量构成的空间为 CC,包含 16 个码字。它的补空间是

C={xxc=0cC}C^{\perp}=\{x \mid x \cdot c=0 \forall c \in C\}

对应的生成矩阵是

H=(000111101100111010101)H=\left(\begin{array}{lllllll}0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right)

它们具有性质 GHT=0GH^T=0

定理

一个码 CC 如果码字间最小的非零距离是 dd,那么码可以校正 t=(d1)/2t=(d-1)/2 个错误,检出 d1d-1 个错误。

编码过程

将 m 编码为 mGmG

解码过程

设收到的信息为 r=mG+er=mG+e,则

rHT=(mG+e)HT=eHTr H^{T}=(m G+e) H^{T}=e H^{T}

则结果对应于 HTH^T 的某一行,通过这个信息可以得出 ee

量子

编码过程

0L=18cHc|0\rangle_{L}=\frac{1}{\sqrt{8}} \sum_{c \in H}|c\rangle 1L=18cHc1111111|1\rangle_{L}=\frac{1}{\sqrt{8}} \sum_{c \in H}|c \oplus 1111111\rangle

解码过程

计算特征:

(b4b5b6b7,b2b3b6b7,b1b3b5b7)\left(b_{4} \oplus b_{5} \oplus b_{6} \oplus b_{7}, \quad b_{2} \oplus b_{3} \oplus b_{6} \oplus b_{7}, \quad b_{1} \oplus b_{3} \oplus b_{5} \oplus b_{7}\right)

可以判断出哪个位出现翻转错误。类似地,由于这种码对 n 元 Hadamard 变换具有不变性

H70L=12(0L+1L)H^{\otimes 7}|0\rangle_{L}=\frac{1}{\sqrt{2}}\left(|0\rangle_{L}+|1\rangle_{L}\right) H71L=12(0L1L)H^{\otimes 7}|1\rangle_{L}=\frac{1}{\sqrt{2}}\left(|0\rangle_{L}-|1\rangle_{L}\right)

同理,一个逻辑的 σx\sigma_x 即是 σx7\sigma_x^7σz\sigma_z 也是如此。

符号翻转错误可以用两种方式